#include <iostream>
#include <vector>

using namespace std;

// 快排
int partition(vector<int>& nums, int left, int right){
    int pivot = nums[right];
    int cur = left;
    for(int i = left; i < right; ++i){
        if(nums[i] < pivot){
            swap(nums[i], nums[cur++]);
        }
    }
    swap(nums[right], nums[cur]);
    return cur;
}
void quicksort(vector<int>& nums, int left, int right){
    if(left >= right) return;
    int mid = partition(nums, left, right);
    quicksort(nums, left, mid - 1);
    quicksort(nums, mid + 1, right);
}

// 希尔
void shellsort(vector<int>& nums){
    int n = nums.size();
    for(int gap = n / 2; gap > 0; gap /= 2){
        for(int i = gap; i < n; ++i){
            int temp = nums[i];
            int j;
            for(j = i; j >= gap && nums[j - gap] > temp; j -= gap)
                nums[j] = nums[j - gap];
            nums[j] = temp;
        }
    }
}

// 归并
void merge(vector<int>& nums, int left, int right, int mid){
    vector<int> temp(right - left + 1);
    int p1 = left, p2 = mid + 1, i = 0;
    while(p1 <= mid && p2 <= right){
        temp[i++] = nums[p1] < nums[p2] ? nums[p1++] : nums[p2++];
    }
    copy(nums.begin() + p1, nums.begin() + mid + 1, temp.begin() + i);
    copy(nums.begin() + p2, nums.begin() + right + 1, temp.begin() + i);
    copy(temp.begin(), temp.end(), nums.begin() + left);
}
void mergesort(vector<int>& nums, int left, int right){
    if(left >= right) return;
    int mid = left + (right - left) / 2;
    mergesort(nums, left, mid);
    mergesort(nums, mid + 1, right);
    merge(nums, left, right, mid);
}


int main(){
    vector<int> nums = {3,5,2,4,1,6};
    // quicksort(nums, 0, nums.size() - 1);
    // shellsort(nums);
    mergesort(nums, 0, nums.size() - 1);
    for(int x : nums) cout << x << " ";
}